class Number < Struct.new(:value)
	def to_s
		value.to_s
	end
	def inspect
		"<#{self}>"
	end
	#规约
	def reducible?
		false
	end
end

class Add < Struct.new(:left, :right)
	def to_s
		"#{left} + #{right}"
	end
	def inspect	
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		if left.reducible?
			Add.new(left.reduce(environment), right)
		elsif right.reducible?
			Add.new(left, right.reduce(environment))
		else
			Number.new(left.value + right.value)
		end
	end
end

class Multiply < Struct.new(:left, :right)
	def to_s
		"#{left} * #{right}"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		if left.reducible?
			Multiply.new(left.reduce(environment), right)
		elsif right.reducible?
			Multiply.new(left, right.reduce(environment))
		else
			Number.new(left.value * right.value)
		end
	end
end

class Bollean < Struct.new(:value)
	def to_s
		value.to_s
	end
	def inspect
		"#{self}"
	end
	def reducible?
		false
	end
end

class LessThan < Struct.new(:left, :right)
	def to_s
		"#{left} < #{right}"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		if left.reducible?
			LessThan.new(left.reduce(environment), right)
		elsif right.reducible?
			LessThan.new(left, right.reduce(environment))
		else
			Bollean.new(left.value < right.value)
		end
	end
end


class Variable < Struct.new(:name)
	def to_s
		name.to_s
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		environment[name]
	end
end

class Machine01 < Struct.new(:expr, :environment)
	def step
		self.expr = expr.reduce(environment)
	end
	def run
		while expr.reducible?
			puts expr
			step
		end
		puts expr
	end
end

#Machine01.new(Add.new(Variable.new(:x), Variable.new(:y)), {x:Number.new(3), y:Number.new(2)}).run

class DoNothing
	def to_s
		"DoNothing"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		false
	end
	def ==(other_statement)
		other_statement.instance_of?(DoNothing)
	end
end

class Assign < Struct.new(:name, :expr)
	def to_s
		"#{name} = #{expr}"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		if expr.reducible?
			[Assign.new(name, expr.reduce(environment)), environment]
		else
			[DoNothing.new, environment.merge({name => expr})]
		end
	end
end

class Machine02 < Struct.new(:statement, :environment)
	def step
		self.statement, self.environment = statement.reduce(environment)
	end
	def run
		while statement.reducible?
			puts "#{statement} #{environment}"
			step
		end
		puts "#{statement} #{environment}"
	end
end

#Machine02.new(Assign.new(:x, Add.new(Variable.new(:y), Number.new(3))), {x:Number.new(1), y:Number.new(2)}).run

class If < Struct.new(:condition, :consequence, :alternative)
	def to_s
		"If(#{condition}) {#{consequence}} else {#{alternative}}"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		if condition.reducible?
			[If.new(condition.reduce(environment), consequence, alternative), environment]
		else
			case condition
			when Bollean.new(true)
				[consequence, environment]
			when Bollean.new(false)
				[alternative, environment]
			end
		end
	end
end

#Machine02.new(If.new(Variable.new(:x), Assign.new(:y, Number.new(1)), Assign.new(:y, Number.new(2))), {x:Bollean.new(true)}).run
#Machine02.new(If.new(Variable.new(:x), Assign.new(:y, Number.new(1)), DoNothing.new), {x:Bollean.new(false)}).run

class Sequence < Struct.new(:first, :last)
	def to_s
		"#{first} ; #{last}"
	end
	def inspect
		"#{self}"
	end
	def reducible?
		true
	end
	def reduce(environment)
		case first
		when DoNothing.new
			[last, environment]
		else
			reduced_first, reduced_environment = first.reduce(environment)
			[Sequence.new(reduced_first, last), reduced_environment]
		end
	end	
end

#Machine02.new(Sequence.new(Assign.new(:x, Add.new(Number.new(1), Number.new(2))), Assign.new(:y, Number.new(3))), {}).run

class While < Struct.new(:condition, :body)
	def to_s
		"While(#{condition}) {#{body}}"
	end
	def inspect
		"<#{self}>"
	end
	def reducible?
		true
	end
	def reduce(environment)
		[If.new(condition, Sequence.new(body, self), DoNothing.new), environment]
	end
end

#Machine02.new(While.new(LessThan.new(Variable.new(:x), Number.new(3)), Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))), {x:Number.new(0)}).run

class Number
	def evaulate(environment) 
		self
	end
end

class Add
	def evaulate(environment)
		Number.new(left.evaulate(environment).value + right.evaulate(environment).value)
	end
end

class Multiply
	def evaulate(environment)
		Number.new(left.evaulate(environment).value * right.evaulate(environment).value)
	end
end

class Bollean
	def evaulate(environment)
		self
	end
end

class LessThan
	def evaulate(environment)
		Bollean.new(left.evaulate(environment).value < right.evaulate(environment).value)
	end
end

class Variable
	def evaulate(environment)
		environment[name]
	end
end

class DoNothing
	def evaulate(environment)
		self
	end
end

class Assign
	def evaulate(environment)
		environment.merge({name => expr.evaulate(environment)})
	end
end

#puts Assign.new(:x, Add.new(Number.new(2), Multiply.new(Variable.new(:x), Number.new(3)))).evaulate({x:Number.new(2)})

class If
	def evaulate(environment)
		case condition.evaulate(environment)
		when Bollean.new(true)
			consequence.evaulate(environment)
		when Bollean.new(false)
			alternative.evaulate(environment)
		end
	end
end

#puts If.new(LessThan.new(Variable.new(:x), Number.new(3)), Assign.new(:x, Number.new(1)), Assign.new(:x, Number.new(0))).evaulate({x:Number.new(2)})

class Sequence
	def evaulate(environment)
		last.evaulate(first.evaulate(environment))
	end
end

#puts Sequence.new(Assign.new(:x, Number.new(1)), Assign.new(:y, Number.new(2))).evaulate({})

class While
	def evaulate(environment)
		case condition.evaulate(environment)
		when Bollean.new(true)
			evaulate(body.evaulate(environment))
		when Bollean.new(false)
			environment
		end
	end
end

#puts While.new(LessThan.new(Variable.new(:x), Number.new(10)), Assign.new(:x, Multiply.new(Variable.new(:x), Number.new(3)))).evaulate({x:Number.new(1)})

class Number
	def to_ruby
		"->e{#{value.inspect}}"
	end
end

class Add
	def to_ruby
		"->e{(#{left.to_ruby}).call(e) + (#{right.to_ruby}).call(e)}"
	end
end

class Multiply
	def to_ruby
		"->e{(#{left.to_ruby}).call(e) * (#{right.to_ruby}).call(e)}"
	end
end

class Bollean
	def to_ruby
		"->e{#{value.inspect}}"
	end
end


class LessThan
	def to_ruby
		"->e{(#{left.to_ruby}).call(e) < (#{right.to_ruby}).call(e)}"
	end
end

class Variable
	def to_ruby
		"->e{e[#{name.inspect}]}" 
	end
end

#puts eval(Multiply.new(Number.new(2), Variable.new(:x)).to_ruby).call({x:Number.new(3)})

class DoNothing
	def to_ruby
		"->e{e}"
	end
end

class Assign
	def to_ruby
		"->e{e.merge({#{name.inspect} => (#{expr.to_ruby}).call(e)})}"
	end
end

class If 
	def to_ruby
		"->e{if (#{condition.to_ruby}).call(e) then (#{consequence.to_ruby}).call(e) else (#{alternative.to_ruby}).call(e) end}"
	end
end

#puts eval(If.new(LessThan.new(Variable.new(:x), Number.new(2)), Assign.new(:x, Number.new(2)), DoNothing.new).to_ruby).call({x:1})

class Sequence
	def to_ruby
		"->e{(#{last.to_ruby}).call((#{first.to_ruby}).call(e))}"
	end
end

class While
	def to_ruby
		"->e{while (#{condition.to_ruby}).call(e); e =  (#{body.to_ruby}).call(e); end; e}"
	end
end

#puts eval(While.new(LessThan.new(Variable.new(:x), Number.new(3)), Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))).to_ruby).call({x:1})

